import java.util.*;

public class Solution218 {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        //有序集合set按x坐标升序存储点
        TreeSet<List<Integer>> set = new TreeSet<>(Comparator.comparingInt(a -> a.get(0)));
        //添加一个x<0的点，方便之后查找建筑是否会被覆盖
        set.add(List.of(-1, 0));
        for (int[] building : buildings) {
            List<Integer> left = Arrays.asList(building[0], building[2]);
            List<Integer> right = Arrays.asList(building[1], 0);
            //获得当前建筑左边的邻点（不重合），用于确定点left是否要添加
            List<Integer> pre = set.lower(left);
            //获得当前建筑右边界范围内最左边的点（可重合），不包括该建筑的左边界，用于确定right是否要添加和高度
            List<Integer> next = set.floor(right);
            int height = building[2], preHeight = pre.get(1);
            //如果左边点比建筑低，那么添加left，如果存在x重合，添加会失败，重合点的高度会在迭代过程中处理
            if (pre.get(1) < height) {
                set.add(left);
            }
            //如果next比建筑低，那么以next为高度添加一个点，可能会添加失败，重合点的高度是原来点的高度
            if (next.get(1) < height) {
                right.set(1, next.get(1));
                set.add(right);
            }
            //迭代[left,right)，维护前一个点的高度，如果当前点将和前一个点在同一高度，删除该点，
            //使用Iterator，它可以在迭代过程中移除元素而不产生异常
            for (Iterator<List<Integer>> iter = set.subSet(left, right).iterator(); iter.hasNext(); ) {
                List<Integer> point = iter.next();
                int curHeight = point.get(1);
                if (curHeight <= height) {
                    if (preHeight == height) {
                        iter.remove();
                    } else {
                        point.set(1, height);
                        preHeight = height;
                    }
                } else {
                    preHeight = curHeight;
                }
            }
        }
        set.pollFirst();
        return new ArrayList<>(set);
    }
}
